By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 29, Issue 4, pp. 1051-1400

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Near-Optimal Parallel Prefetching and Caching

Tracy Kimbrel and Anna R. Karlin

pp. 1051-1082

BibTeX  Abstract Full Text:  PDF

Complexity Results for First-Order Two-Variable Logic with Counting

Leszek Pacholski, WiesL aw Szwast, and Lidia Tendera

pp. 1083-1117

BibTeX  Abstract Full Text:  PDF

Making Nondeterminism Unambiguous

Klaus Reinhardt and Eric Allender

pp. 1118-1131

BibTeX  Abstract Full Text:  PDF

A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem

Oded Goldreich and Shmuel Safra

pp. 1132-1154

BibTeX  Abstract Full Text:  PDF

Verification of Identities

Sridhar Rajagopalan and Leonard J. Schulman

pp. 1155-1163

BibTeX  Abstract Full Text:  PDF

Exploring Unknown Environments

Susanne Albers and Monika R. Henzinger

pp. 1164-1188

BibTeX  Abstract Full Text:  PDF

Reducibility and Completeness in Private Computations

Joe Kilian, Eyal Kushilevitz, Silvio Micali, and Rafail Ostrovsky

pp. 1189-1208

BibTeX  Abstract Full Text:  PDF

Lower Bounds for (MODp - MODm) Circuits

Vince Grolmusz and Gábor Tardos

pp. 1209-1222

BibTeX  Abstract Full Text:  PDF

Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane

Danny Z. Chen, Kevin S. Klenk, and Hung-Yi T. Tu

pp. 1223-1246

BibTeX  Abstract Full Text:  PDF

Reducing Randomness via Irrational Numbers

Zhi-Zhong Chen and Ming-Yang Kao

pp. 1247-1256

BibTeX  Abstract Full Text:  PDF

On the Power of Logic Resynthesis

Wei-Liang Lin, Amir H. Farrahi, and M. Sarrafzadeh

pp. 1257-1289

BibTeX  Abstract Full Text:  PDF

Application-Controlled Paging for a Shared Cache

Rakesh D. Barve, Edward F. Grove, and Jeffrey Scott Vitter

pp. 1290-1303

BibTeX  Abstract Full Text:  PDF

Perfect-Information Leader Election with Optimal Resilience

Ravi B. Boppana and Babu O. Narayanan

pp. 1304-1320

BibTeX  Abstract Full Text:  PDF

Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout

Alok Aggarwal, Jon Kleinberg, and David P. Williamson

pp. 1321-1333

BibTeX  Abstract Full Text:  PDF

Quality Mesh Generation in Higher Dimensions

Scott A. Mitchell and Stephen A. Vavasis

pp. 1334-1370

BibTeX  Abstract Full Text:  PDF

Containment and Optimization of Object-Preserving Conjunctive Queries

Edward P. F. Chan and Ron van der Meyden

pp. 1371-1400

BibTeX  Abstract Full Text:  PDF